package com.leetcode.partition3;

/**
 * @author `RKC`
 * @date 2021/8/5 10:11
 */
public class LC263丑数 {

    /**
     * 如何判定一个数是丑数？
     *
     * 已知给定一个数n，我们先判断它能被2，3，5哪个数整除。
     * 但是呢，能被2，3，5整除的数也不一定丑数。比如14，可以被2整除，但是也可以被7整除。怎么能够排除这种数呢，很简单
     * 只要把给定的数字n被2，3，5除到商只剩1就好了
     * 具体怎么操作呢？
     *
     * 在除之前，先判断当前的数能不能被2，3，5整除，用取余符号%。可以被整除的话，就把商作为下一次递归需要的参数传入
     * 可知在被除尽之后，只要商为1，就是递归的终点，并且我们可以认为是丑数，返回true
     * 若商不为1，且无法再被2，3，5整除（例如商为7），那就不是丑数，直接返回false
     * 0直接返回false
     * @param n
     * @return
     */
    public static boolean isUgly(int n) {
        if (n == 0) return false;
        else if (n == 1) return true;

        if (n % 2 == 0) return isUgly(n / 2);
        if (n % 3 == 0) return isUgly(n / 3);
        if (n % 5 == 0) return isUgly(n / 5);
        return false;
    }

    public static void main(String[] args) {
        System.out.println(isUgly(11));
    }
}
